home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c / 623 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  2.6 KB
  1. Path: tbj.dec.com!diamond
  2. From: diamond@tbj.dec.com (Norman Diamond)
  3. Newsgroups: comp.std.c
  4. Subject: Re: Restrictions on qsort compare function?
  5. Date: 22 Mar 1996 02:58:51 GMT
  6. Organization: Digital Equipment Corporation Japan , Tokyo
  7. Message-ID: <4it51b$ng8@usenet.pa.dec.com>
  8. References: <4iokop$h4p@lyra.csx.cam.ac.uk> <4iqjar$2m9@usenet.pa.dec.com> <1996Mar21.113301.2622@sq.com>
  9. Reply-To: diamond@tbj.dec.com (Norman Diamond)
  10. NNTP-Posting-Host: jit533.tbj.dec.com
  11.  
  12. In article <1996Mar21.113301.2622@sq.com>, msb@sq.com (Mark Brader) writes:
  13. #  The function shall return an integer less than, equal to, or greater
  14. #  than zero if the first argument is considered to be respectively
  15. #  less than, equal to, or greater than the second.
  16.  
  17. >In other words, it must yield an ordering of the possible data values.
  18. >This is only the case if
  19. >
  20. >1. It is a pure function:
  21. >   repeated calls to compar(x,y) yield a result having the
  22. >       same sign each time
  23. >
  24. >2. It is antisymmetric (I think that's the right word):
  25. >   if compar(x,y) <  0, then compar(y,x) >  0
  26. >   if compar(x,y) == 0, then compar(y,x) == 0
  27. >   if compar(x,y) >  0, then compar(y,x) <  0
  28. >
  29. >3. If is transitive:
  30. >   if compar(x,y) > 0 && compar(y,z) > 0, then compar(x,z) > 0
  31.  
  32. You have given an intuitively and logically reasonable definition of a
  33. comparison system, but the standard does not.  The standard has trouble
  34. defining a pure binary numeration system and even has trouble refering
  35. to a document which did it.  Until the standard finds a definition of a
  36. comparison system, it is defective.
  37.  
  38. >>>On tracking down a bug in some old code I noticed that we had the
  39. >>>compare function returning something like "a > b" instead of "b - a".
  40.  
  41. >>Just one sentence earlier, you gave the exact reason why
  42. >>it doesn't matter if you do "a > b" instead of "a - b".
  43.  
  44. >Of course it matters.  With this function, if compar(x,y) > 0, then
  45. >compar(y,x) == 0.  This is not antisymmetric.
  46.  
  47. Argh!  I was remembering what the hardware usually does for comparison
  48. instructions, and forgot that C operators lose part of that information.
  49. I must be getting Cnile.
  50.  
  51. >(a > b)? 1: (a < b)? -1: 0
  52.  
  53. Yup.  Incidentally, do you think the average implementation's
  54. interprocedural optimization phase will change this user function into
  55. one machine instruction in the library's qsort() function :-?
  56. --
  57.  <<  If this were the company's opinion, I would not be allowed to post it.  >>
  58. "I paid money for this car, I pay taxes for vehicle registration and a driver's
  59. license, so I can drive in any lane I want, and no innocent victim gets to call
  60. the cops just 'cause the lane's not goin' the same direction as me" - J Spammer
  61.